#include <stdio.h>
#include <assert.h>

int main()
{
  int m, n, q, r, a, b, ap, bp, c, d, t;
  printf("Podaj m > 0 : "); scanf("%i", &m);
  printf("Podaj n > 0 : "); scanf("%i", &n);
  assert(m > 0); assert(n > 0);   // asercja A1
  printf("NWD(%i, %i) = ", m, n);
 E1: // inicjowanie
  ap = 1; b = 1; a = 0; bp = 0; c = m; d = n;
  assert(c > 0); assert(d >0); assert(a == 0); assert(bp == 0); assert(ap == 1); assert(b == 1); // asercja A2
 E2: // dzielenie
  r = c%d;
  q = c/d;
  assert(a*m+b*n == d); assert(ap*m+bp*n == c); assert(q*d+r == c); assert(r < d && 0 <= r);   // asercja A3
 E3: // czy reszta zero?
  if (r == 0){
    assert(a*m+b*n == d);     // asercja A4
    printf("%i = %i*%i + %i*%i\n", d, a, m, b, n);
    return 0;
  };
  assert(a*m+b*n == d); assert(ap*m+bp*n == c); assert(q*d+r == c); assert(r < d && 0 < r);   // asercja A5
 E4: // ponowienie
  c = d; d = r; t = ap; ap = a; a = t-q*a; t = bp; bp = b; b = t-q*b;
  assert(a*m+b*n == d); assert(ap*m+bp*n == c); assert(d > 0);   // asercja A6
  goto E2;
}

